// 先来描述一下问题吧，就是一个图里，有不同的连通分支，然后找图里的两点是否是连通的,回答是否连通就可以
// 还有一个操作就是将两个点相连接
// 类比现实实际是个复杂的网络图那种
//第一个要求是先输入一个数N，然后输入N个无序对，判断每一个无序对是否相连接，如果不是，那么将他们连接起来
//上面的要求，需要将那些无序对输入到一个对象中存储，用一个数组存储
//第一个要求完毕就可以开始写快速查找算法（eager algorithm）
//先是用一个数组去存储id，每个连通分支只有一个id入口，就是假如0,3,5连通，那么0，3,5的入口可以都是0，也就是数组5对应的位
//置存储的是0，用来说明5和0在一个连通分支，其他连通分支同理
//这样快速查找算法就非常简单了，单纯比较就可以
//union也不过是多加了一个改变编号的事，一个个判断，然后改变编号，因为需要调用m次，而算法的时间复杂度是O(n)，那么总共需要
//花费的时间就是平方级别的，这就有一点长了
//所以要用quick union
//这个是想象其为一个森林，同样的数组里每个点对应的下标存放的是其父母结点的下标
//这样每次union的时候只需要将根节点下标更改即可
//但是这样查找就更麻烦，需要一个一个地向上查找根节点
//那么下面是再次的改进
//改进之后，总是让较小的（深度比较低）的树成为较大树的孩子，不过这里需要用一个额外的数组去记录每个树的权（深度或者结点个数），
//这样时间复杂度就是M*NlogN
//通过路径压缩，可以再次进行优化 也就是说，在寻找根结点的时候，可以加一步将其存放的父结点改为祖父结点，
//这样时间复杂度就接近线性了
//用渗透来举例讲讲应用
//就是一个n*n的方格中有白点有黑点占据位，白的开放的，概率为p，黑的闭合的，概率为（1-p），这时如果系统是渗透的
//那么就可以找到一条通过白色方格从上到下的路径
//这时候我们可以知道，当p大的时候会有通路，p小的时候没有通路，关键在于p介于中间值的时候
//有一个值大于他一定会有通路，小于他基本不会有通路，为了找出这个值
//这个时候可以用蒙特卡洛仿真模拟
//就是首先系统都是闭合的，然后随机一个个地给出开放点，检测是否变成了渗透的系统
//检测的时候可以在顶端和低端加上虚拟根结点去检测
//开放新位的时候将那个位和周围的位相连接
import java.util.Scanner;
import java.util.Random;
public class App {
    static int  choise=0;     //等于1时手动测试，等于0时自动测试
    public static void main(String[] args) throws Exception {
        if(choise==1)     //手动
       {
        System.out.printf("输入键值个数:");
        Scanner scanner = new Scanner(System.in);
        int number = scanner.nextInt();            //获得整数输入
        union_find_v0 test=new union_find_v4(number);   //构造对象
        System.out.printf("输入键值对个数:");
        int number2 = scanner.nextInt();             //获得整数输入
        int a=0,b=0;
        for(int i=0;i<number2;i++)
        {
            System.out.printf("输入第%d个键值对",i+1);
            a=scanner.nextInt();
            b=scanner.nextInt();
            test.union(a,b);
        }

        System.out.printf("输入测试连通性: ");
        int x = scanner.nextInt();
        int y = scanner.nextInt();
        if (test.connected(x, y)) {
            System.out.println(x + " 和 " + y + " 是连通的。");
        } else {
            System.out.println(x + " 和 " + y + " 不是连通的。");
        }
        scanner.close();
        }

        else     //自动
        {
            
            int n = 100000; // 10 万个元素
            int operations = 50000; // 5 万次操作
            union_find_v0 uf = new union_find_v4(n);
            Random rand = new Random();
            // 随机合并 5 万对
            long start = System.nanoTime();
            for (int i = 0; i < operations; i++) {
                int a = rand.nextInt(n);
                int b = rand.nextInt(n);
                uf.union(a, b);
            }
    
            long mid = System.nanoTime();
            // 随机查询 1000 次
            int correct = 0;
            for (int i = 0; i < 10000; i++) {
                int a = rand.nextInt(n);
                int b = rand.nextInt(n);
                boolean expected = uf.connected(a, b); // 直接查询
                if (expected) correct++;
            }
            long end = System.nanoTime();
            System.out.println("连通查询测试通过数：" + correct + " / 10000");

            System.out.println("合并时间：" + (mid - start) / 1e6 + " ms");
            System.out.println("查找时间：" + (end - mid) / 1e6 + " ms");
        }
    }
}
